/** 
 * 获取字符串的前缀表；
 * KMP算法的核心，时间复杂度O(n)
 * @param s 字符串
 * @returns 前缀表
 */
export const getPrefix = (s: string): number[] => {
  //初始化
  let j = 0,
    prefix: number[] = [];
  prefix[0] = j;

  for (let i = 1; i < s.length; i++) {
    //处理前后缀不相同的情况
    while (j > 0 && s[i] != s[j]) {
      j = prefix[j--];
    }
    //处理前后缀相同的情况
    if (s[i] === s[j]) j++;
    prefix[i] = j;
  }
  return prefix;
};

/** 
 * 重复的子字符串
 * @param s 字符串
 * @returns  boolean
 */
export function repeatedSubstringPattern(s: string): boolean {
  let next = getPrefix(s);
  let sLength = s.length;
  let nextLength = next.length;
  let suffixLength = next[nextLength - 1];
  if (suffixLength > 0 && sLength % (sLength - suffixLength) === 0) return true;
  return false;
}

/**
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。
 * 如果不存在，则返回  -1。
 * @param haystack 文本串
 * @param needle 模式串
 * @returns
 */
export function strStr(haystack: string, needle: string): number {
  if (needle.length === 0) return 0;
  let next: number[] = getPrefix(needle);
  let j: number = 0;

  for (let i = 0, length = haystack.length; i < length; i++) {
    while (j > 0 && haystack[i] !== needle[j]) {
      j = next[j - 1];
    }
    if (haystack[i] === needle[j]) {
      if (j === needle.length - 1) {
        return i - j;
      }
      j++;
    }
  }
  return -1;
}

/** 
 * 左旋转字符串
 * 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
 * 请定义一个函数实现字符串左旋转操作的功能。
 * 比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
 * @param s
 * @param n
 * @returns
 */
export function reverseLeftWords(s: string, n: number): string {
  return (s + s).slice(n, s.length + n);
}

/** 
 * 反转字符串II
 * 给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
 * @param s
 * @param k
 * @returns
 */
export function reverseStr(s: string, k: number): string {
  let left: number, right: number;
  let arr: string[] = s.split("");
  let temp: string;
  for (let i = 0, length = arr.length; i < length; i += 2 * k) {
    left = i;
    right = i + k - 1 >= length ? length - 1 : i + k - 1;
    while (left < right) {
      temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }
  return arr.join("");
}

/** 反转字符串
 *
 * @param s
 */
export function reverseString(s: string[]): void {
  let l = -1,
    r = s.length;
  while (++l < --r) [s[l], s[r]] = [s[r], s[l]];
}
